package com.company;

public class SelectionSort {
    private SelectionSort() {
    }

    public static <E extends Comparable<E>> void sort(E[] arr) {
        //arr[0..i]有序的arr[i..n]无需的
        //arr[0..i] [i..n)循环不变量是什么？
        //还是泛型类的方式
        //arr[0] -0-n的方式 arr[0=minxindex arr[minxex]=arr[0]
        // arr[1..n]arr[i]= arr[minxindex]
        //minx
        // arr[j]=arr[t]
        //循环不变量的方式
        for (int i = 0; i < arr.length; i++) {
            //选择 arr[i..n] 中最小值的索引
            int minIndex = i;
            for (int j = i; j < arr.length; j++) {
                if (arr[j].compareTo(arr[minIndex]) < 0) {
                    minIndex = j;
                }
            }
            swap(arr, i, minIndex);
        }
    }

    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    public static void main(String[] args) {
        int[] dataSize = {1000, 10000};
        for (int n : dataSize) {
            Integer[] arr = ArrayGenerator.generateRandomArray(n, n);
            SortingHelper.sortTest(SortFunctionEum.SelectionSort, arr);
        }
        //随着你的数据规模你的性能 怎么不看好
        // 对算法性能也好 反省自定义的类型打好的基础
        //还是java系列的模式可以选择的方式
        //插入选择
        //选择排序
        //插入【怕偶
        //插入排序法
        //变的有序
        //每次处理一张票 把这张牌插入到前面已经排序好的插入到合适的位置
        //计算机
        //int[] arr = {6,4,2,3,1,5}
        // minxIndex=i
        //i当前的位置 i=0
        //arr[0,i) arr[i,n)
        // arr[0,0) arr[0,n)
        //把arr[i]放到合适的位置
        // i=0
        //不需要插入任何位置
        //i++
        //arr[1] 需要和j=i,j=j-1;j--
        //arr[1]<arr[0]
        //4就是插入到那个位置
        //i++
        //arr[2] j=2 arr[1] arr[0]
        //2,4,6
        // i++
        // arr3 3  2 1 0
        // 3 6 4
        // 2 3 4 6
        // 1 2 3 4 6
        // 1 2 3 4 5 6
        // n^2 选择排序复杂度
//        Student[] students = {
//                new Student("sin",98),
//                new Student("s",100),
//                new Student("j",66),
//        };
//        SelectionSort.sort(students);
//        for (Student student:students){
//            System.out.println(student+ "");
//            System.out.println();
//        }
        //；类型必须extends Comparable 基于比较的算法
        //基于比较的算法
        // private static <E extends Comparablle<E>> sort(E[]arr)
        // for(int i=0;i<arr.length;i++)
        // minxindex=i
        // for(int j=i;j<arr.length;j++)
        // if(arr[j].compareTo(arr[i))<0)
        // mindex=j
        //swap(arr,i,minxIndex)
        //选择排序法复杂度分析
        // 0 n
        // 1 n-1
        // 2 n-2
        // n-1 1
        // 1+2+n
        // 1+n
        // O n^2
        // 选择排序法的时间性能验证一下
        //
    }
}
